package com.yileiqian.alg;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class MatrixWord {

	public static final int MATRIX_SIZE = 4;

	public static List<String> getAllWords(char[][] matrix) {
		Set<String> results = new HashSet<String>();
		boolean[][] flagMatrix = new boolean[MATRIX_SIZE][MATRIX_SIZE];

		for (int i = 0; i < MATRIX_SIZE; i++) {
			for (int j = 0; j < MATRIX_SIZE; j++) {
				travel(i, j, "", matrix, results, flagMatrix);
			}
		}

		List<String> outlist = new ArrayList<String>();
		for (String s : results) {
			outlist.add(s);
		}
		return outlist;
	}

	private static boolean travel(int x, int y, String path, char[][] matrix,
			Set<String> results, boolean[][] flagMatrix) {
		if (flagMatrix[x][y]) {
			return false;
		}
		String buffer = path + matrix[x][y];
		results.add(buffer);
		flagMatrix[x][y] = true;

		if (x - 1 > 0) {
			if (travel(x - 1, y, buffer, matrix, results, flagMatrix)) {
				flagMatrix[x - 1][y] = false;
			}
		}
		if (x + 1 < MATRIX_SIZE) {
			if (travel(x + 1, y, buffer, matrix, results, flagMatrix)) {

				flagMatrix[x + 1][y] = false;
			}
		}
		if (y - 1 > 0) {
			if (travel(x, y - 1, buffer, matrix, results, flagMatrix)) {
				flagMatrix[x][y - 1] = false;
			}
		}
		if (y + 1 < MATRIX_SIZE) {
			if (travel(x, y + 1, buffer, matrix, results, flagMatrix)) {
				flagMatrix[x][y + 1] = false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		Random r = new Random();
		char[][] matrix = new char[MATRIX_SIZE][MATRIX_SIZE];

		for (int i = 0; i < MATRIX_SIZE; i++) {
			for (int j = 0; j < MATRIX_SIZE; j++) {
				matrix[i][j] = (char) (97 + r.nextInt(26));
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}

		for (String s : getAllWords(matrix)) {
			System.out.println(s);
		}

	}
}
